package main

import (
	"fmt"
	"strings"
	//"errors"
	//"strconv"
)

func main(){

	 var list =  []int{1,5,4,2,6,7,3}
	// fmt.Printf("冒泡排序:%T,%v\n",list,bubblesort(list))
	// list =  []int{3,5,8,1,2,9,4,7,6}
	 fmt.Printf("快速排序:%T,%v\n",list,fastsort(list))

	///fmt.Printf("61 = %v,62 = %v",to62RadixString(61),to62RadixString(62))
	
}
	/*
	冒泡排序
	step
	1、比较相邻元素，如果前一个比后一个大，就交换他们位置
	2、对每一对相邻元素作同样工作，从开始第一对到最后一对，做完后，最后一个会是最大数
	3、针对所有元素重复以上步骤，除了最后一个
	4、持续每次对越来越少的元素重复衣裳步骤，直到没有任何一对数字需要比较
	*/
func bubblesort(liner []int)(line []int){
	var length =len(liner)
	for i:=0;i<length;i++{
		for j:=0;j<length-1-i;j++{
			if liner[j]>liner[j+1]{
				liner[j],liner[j+1] = liner[j+1],liner[j]
			}
		}
	}
	line = liner 
	return
}
	/*
	快速排序-分而治知
	step
	1、选出一个基准(pivot)
	2、重新排列序列、对数列进行分区(partition),
	3、递归(recursive),把小于基准的数列和大于基准的数列进行递归排序
	底部情况是，数列的大小是0或者1，也就是永远都已经排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代(iteration)中,他至少会把一个元素摆到它最后的位置去
	*/

func fastsort(list []int)[]int{
	return _fastsort(list,0,len(list)-1)
}
func _fastsort(list []int,l,r int)[]int{
	if l<r {
		part := part(list,l,r)
		_fastsort(list,l,part-1)
		_fastsort(list,part+1,r)
	}
	return list
}
func part(list []int,l,r int)int{
	var pivot=l
	index:=pivot+1 
	for i:=index;i<=r;i++ {
		if list[i]<list[pivot] {
			swap(list,i,index)
			index++
		}
	}
	index--
	swap(list,index,pivot)

	return index
}
func swap(list []int,l,r int){
	list[l],list[r] = list[r],list[l]
}

/*62位URL短地址*/
var DIGITS = []string{ "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D",
"E", "F", "G", "H", "I", "J", "K", "L", "M", "N",
"O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z","a", "b", "c", "d", "e", "f", "g", "h", "i", "j",
"k", "l", "m", "n", "o", "p", "q", "r", "s", "t",
"u", "v", "w", "x", "y", "z"}

func to62RadixString(num int)string{
	var length = len(DIGITS)
	var slice  = make([]string,length)
	var index = 0
	for {
		var mod = num%length
		slice[index] = DIGITS[mod]
		num = num/length
		if num == 0 {
			break;
		}
		index++;
	}
	reverse(slice)
	return strings.Join(slice,"")
}
func reverse(s []string) {
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		s[i], s[j] = s[j], s[i]
	}
}
